package 力扣._00周赛._428周赛.问题3;

import java.util.HashMap;
import java.util.Map;

class Solution2 {
    public int beautifulSplits(int[] nums) {
        int n = nums.length;
        // 用于记录每个数字在每个位置之后第一次出现的位置
        Map<Integer, Integer>[] nextPos = new Map[n];
        for (int i = 0; i < n; i++) {
            nextPos[i] = new HashMap<>();
        }
        // 预处理每个数字在每个位置之后第一次出现的位置
        for (int i = n - 2; i >= 0; i--) {
            Map<Integer, Integer> curMap = nextPos[i];
            Map<Integer, Integer> nextMap = nextPos[i + 1];
            for (Map.Entry<Integer, Integer> entry : nextMap.entrySet()) {
                curMap.put(entry.getKey(), entry.getValue());
            }
            curMap.put(nums[i + 1], i + 1);
        }
        int[] dp = new int[n];
        for (int j = 1; j < n - 1; j++) {
            // 判断nums[0...j-1]是否是nums[j...n-1]的前缀
            boolean isPrefix = checkPrefix(nums, 0, j, nextPos[j]);
            if (isPrefix) {
                dp[j]++;
            }
            for (int k = j + 1; k < n; k++) {
                // 判断nums[j...k-1]是否是nums[k...n-1]的前缀
                isPrefix = checkPrefix(nums, j, k, nextPos[k]);
                if (isPrefix) {
                    dp[k] += dp[j];
                }
            }
        }
        int count = 0;
        for (int num : dp) {
            count += num;
        }
        return count;
    }

    private boolean checkPrefix(int[] nums, int start, int end, Map<Integer, Integer> nextPos) {
        for (int i = start; i < end; i++) {
            if (!nextPos.containsKey(nums[i])) {
                return false;
            }
            int nextIndex = nextPos.get(nums[i]);
            if (nextIndex < end) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
//        int[] nums = {2,3,2,2,1};
        int[] nums = {1,1,2,1};
//        int len = 5000;
//        int[] nums = new int[len];
//        for (int i = 0; i < len; i++) {
//            nums[i] = 1;
//        }
        System.out.println(solution.beautifulSplits(nums));
    }
}